package net.tp.algo.text.sa;

import net.tp.algo.text.SuffixTree;
import static net.tp.util.Utils.*;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * <p>Build longest common prefix array using suffix tree.</p>
 *
 * <pre>
 *  ┌────┬─────┴───┬─────┐
 *  ¥    a         b     n
 *  6  ┌─╨───┐     a     a
 *     ¥     n     n   ┌─┴─┐
 *    [5]    a     a   ¥   n
 *         ┌─┴─┐   n   4   a
 *         ¥   n   a       ¥
 *        [3]  a   ¥       2
 *             ¥   0
 *             1
 * </pre>
 * <p>Like building suffix array using suffix tree, building LCP array is done by traversing dfs in lexical order. Every
 * time the traversal turns from up to down, the string depth at the node where the turning happens is the next value
 * of lcp. That is because the string depth at that node is the longest common prefix between the last visited leaf node
 * (i.e. a predecessor suffix) with the next to-be-visited leaf node. For example, assuming the las visited leaf node
 * is 5, the next leaf node to visit is 3. During this traversal, the turn from up to down will happen at the internal
 * node with string depth = 1. So the longest common prefix between $S_3$ and $S_5$ is 1.</p>
 *
 * @author Trung Phan
 *
 */
public class ST2LCP {

    public static int[] buildLCP(SuffixTree.Node st) {

        List<Integer> lcp = new ArrayList<>();

        lcp.add(0);
        dfsInLexicalOrder(st, lcp);

        return toIntArray(lcp);
    }

    private static void dfsInLexicalOrder(SuffixTree.Node node, List<Integer> lcp) {

        boolean first = true;
        for (char c : node.edges()) {

            if (first) first = false;
            else lcp.add(node.getStringDepth()); // do not add depth if it's the first.

            SuffixTree.Edge e = node.edge(c);
            if (e.getNextNode() != null) {
                dfsInLexicalOrder(e.getNextNode(), lcp);
            }
        }

    }
}
